#include "./include/MFQ_t.h"
#include <stdlib.h>

/*
 * 定义每个优先级时间片
 * 优先级越高，时间片越少
 */
int priority_time_slices[MFQ_MAXSIZE+1]={
    0,    // 优先级为0时，时间片为0
    16,   // 优先级为1时，时间片为16
    8,    // 优先级为2时，时间片为8
    4,    // 优先级为3时，时间片为4
    2,    // 优先级为4时，时间片为2
    1,    // 优先级为5时，时间片为1
};


/*
 * 函数功能：
 *     创建相关的数据结构结点
 *     并且确保创建成功
 * 参数:
 *     void
 * 返回值:
 *     返回对应的结点指针，并且保证返回值不为空指针
 */ 
ElemNode* createElemNode()
{
    ElemNode* pNode=(ElemNode*)malloc(sizeof(ElemNode));
    pNode->nid=-1;
    pNode->pEelm=NULL;
    pNode->next=NULL;
    return pNode;
}
QueueLink* createQueueLink()
{
    QueueLink* pQL=(QueueLink*)malloc(sizeof(QueueLink));
    pQL->qHead=NULL;
    pQL->qTail=NULL;
    pQL->size=0;
    return pQL;  
}
MFQ_t* createMFQ()
{
    MFQ_t *pMFQ=(MFQ_t *)malloc(sizeof(MFQ_t));
    pMFQ->size=MFQ_MAXSIZE;
    for(int i=0; i<=pMFQ->size; i++) {
        pMFQ->QueueTable[i]=createQueueLink();
    }
    return pMFQ;
}

void addElemNode2QueueLink(QueueLink *pQL, ElemNode *pNode)
{
    if(pQL && pNode) {
        pNode->next=NULL;
        if(pQL->qTail) {
            pQL->qTail->next=pNode;
        }
        pQL->qTail=pNode;
        if(NULL==pQL->qHead) {
            pQL->qHead=pQL->qTail;
        }
        (pQL->size)++;
    }
}

/*
 * 函数功能：
 *     将一个结点元素压入多级反馈队列表 MFQ_t 中
 * 参数：
 *     MFQ_t *pMFQ: 传入一个多级反馈队列表指针
 *     ElemNode *pNode: 传入一个结点指针
 *     int priority: 传入一个优先级
 * 返回值：
 *     void
 */ 
void push(MFQ_t *pMFQ, ElemNode *pNode)
{
    if(pMFQ && pNode) {
        int p=pNode->nid;
        if(1<=p && p<=pMFQ->size) {
            addElemNode2QueueLink(pMFQ->QueueTable[p],pNode);
        }
    }
}

/*
 * 函数功能：
 *     从 MFQ_t 中弹出优先级最大的队列的头结点元素
 * 参数：
 *     MFQ_t *pMFQ: 传入一个多级反馈队列表指针
 * 返回值：
 *     ElemNode* : 返回一个结点元素
 */
ElemNode* pop(MFQ_t *pMFQ)
{
    ElemNode* pNode = NULL;
    if(pMFQ) {
        int p=pMFQ->size;
        while( p>0 && !pMFQ->QueueTable[p]->qHead ) {
             p--;         // 从优先级大到小找到一个不为空的队列
        }
        if(0<p) {
            QueueLink *pQL=pMFQ->QueueTable[p];
            pNode=pQL->qHead;
            pQL->qHead=pQL->qHead->next;
            if(pNode==pQL->qTail) {
                pQL->qTail=pNode->next;
            }
            (pMFQ->QueueTable[p]->size)--;
            pNode->next=NULL;
            pNode->nid=p;  // 结点元素id即为它的优先级
        }
    }
    return pNode;
}

ElemNode* top(MFQ_t *pMFQ)
{
    ElemNode *pNode=NULL;
    if(pMFQ) {
        int p=pMFQ->size;
        while( p>0 && !pMFQ->QueueTable[p]->qHead ) p--;
        if(p>0) {
            pNode=pMFQ->QueueTable[p]->qHead;
            pNode->nid=p;
        }
    }
    return pNode;
}
int top_priority(MFQ_t *pMFQ)
{
    int p=0;
    if(pMFQ) {
        p=pMFQ->size;
        while( p>0 && !pMFQ->QueueTable[p]->qHead ) {
             p--;  // 从优先级大到小找到一个不为空的队列
        }
    }
    return p;
}

/*
 * 函数功能：
 *     多级反馈队列的调度算法
 *     每次取出一个优先级最高的元素返回
 *     同时将每一级队列的队头元素提升一个优先级
 * 参数：
 *     MFQ_t *pMFQ: 传入一个多级反馈队列表指针
 * 返回值：
 *     ElemNode* : 返回一个泛型指针
 */
ElemNode* dispatch(MFQ_t *pMFQ)   // 调度算法
{
    ElemNode* pRetNode=pop(pMFQ);
    if(pRetNode) {
        /*
         * 动态改变优先级
         * 将每个队列的对头元素提升至更高优先级队列的队尾
         */
        int p=pRetNode->nid;
        ElemNode* pNode=NULL;
        while(p>0) {
            if(pMFQ->QueueTable[p-1]->qHead) {
                // 如果下一级队列不为空，则取出队头元素
                pNode=pMFQ->QueueTable[p-1]->qHead;
                pMFQ->QueueTable[p-1]->qHead=pNode->next;
                if(pNode==pMFQ->QueueTable[p-1]->qTail) {
                    pMFQ->QueueTable[p-1]->qTail=pNode->next;
                }
                // 将元素结点加入队列尾部
                addElemNode2QueueLink(pMFQ->QueueTable[p],pNode);
            }
            p--;
        } 
    }
    return pRetNode;
}


